﻿#ifndef __LINEARIZESELECT__
#define __LINEARIZESELECT__
#include <cmath>
#include <algorithm>
using namespace std;

template <class atype>
class LinearizeSelect{
	typedef atype* ArrayPtr;
	static int Partition(ArrayPtr Arr, const int left, const int right);
	static int RandomPartition(ArrayPtr Arr, const int left, const int right);
	static atype GetMedian(ArrayPtr Arr, const int size);
	static atype GetMM(ArrayPtr Arr, const int left, const int right);
	static int MedianPartition(ArrayPtr Arr, const int left, const int right);	
	static atype WorstConditionSelect(ArrayPtr Arr, const int size,
								const int left, const int right, const int index);
	static atype ExpectSelect(ArrayPtr Arr, const int size, 
								const int left, const int right, const int index);
public:
	static atype ExSelect(ArrayPtr Arr, const int size, const int index);
	static atype WCSelect(ArrayPtr Arr, const int size, const int index);
};

template <class atype>
int LinearizeSelect<atype>::Partition(ArrayPtr Arr, const int left, const int right){
	atype key = Arr[right];
	int index = left - 1;
	for(int i = left ; i <= right ; ++i){
		if(Arr[i] <= key) {
			swap(Arr[i] , Arr[++index]);
		}
	}
	return index;
}

template<class atype>
int LinearizeSelect<atype>::RandomPartition(ArrayPtr Arr, const int left, const int right){
	int ran = GetRandom<int>(left, right);
	swap(Arr[ran],Arr[right]);
	return Partition(Arr, left, right);
}

template<class atype>
atype LinearizeSelect<atype>::ExpectSelect(ArrayPtr Arr, const int size, 
								const int left, const int right,const int index){
	if(left == right) return Arr[left];
	int arrIndex = RandomPartition(Arr, left, right);
	int status = arrIndex + 1;
	if(status == index){
		return Arr[arrIndex];
	}else if(status < index){
		return ExpectSelect(Arr, size, arrIndex+1, right, index);
	}else{
		return ExpectSelect(Arr, size, left, arrIndex-1, index);
	}
}

template <class atype>
atype LinearizeSelect<atype>::GetMedian(ArrayPtr Arr, const int size){
	if(size == 1) return Arr[0];
	for(int i = 1; i < size; ++i){
		atype key = Arr[i];
		int j = i-1;
		for(;;){
			if(key >= Arr[j] || j < 0) break;
			Arr[j+1] = Arr[j--];
		}
		Arr[j+1] = key;
	}
	if(size % 2 == 0) return Arr[size/2-1];
	else return Arr[size/2];
}

template <class atype>
atype LinearizeSelect<atype>::GetMM(ArrayPtr Arr, const int left, const int right){
	int size = right - left + 1;
	//将数据划分为5个数据的小数组
	int subCnt = (int)ceil((double)size / 5);
	ArrayPtr midArr = new atype[subCnt];
	ArrayPtr * subArr = new atype*[subCnt];
	for(int p=0 ; p < subCnt; ++p){
		subArr[p] = new atype[5];
	}
	//前面的满数组 subCnt-1 个
	int i = 0,offset = 0;
	for(; i < subCnt-1; ++i,offset+=5){
		for(int j=0; j < 5; ++j){
			int index = left + offset + j;
			if(index <= right)
				subArr[i][j]= Arr[index];
		}
		midArr[i] = GetMedian(subArr[i],5);
	}
	//至多会有一个不满的数组
	int cnt = 0;
	for(int j=0; j<5; ++j){
		int index = left + offset + j;
		if(index <= right){
			subArr[i][j] = Arr[index];
			++cnt;
		}
	}
	//如果都是满数组则可以省略这一步计算
	if( cnt != 0 )
		midArr[i] = GetMedian(subArr[i],cnt);
	//递归调用
	if(subCnt%2 ==0) return WCSelect(midArr, subCnt, subCnt/2);
	else return WCSelect(midArr, subCnt, (int)ceil(subCnt/2.0));

	//清理工作
	delete [] midArr;
	for(int i = 0; i < subCnt; ++i){
		delete [] subArr[i];
	}
	delete [] subArr;
	subArr = NULL;
	midArr = NULL;
}

template <class atype>
int LinearizeSelect<atype>::MedianPartition(ArrayPtr Arr, const int left, const int right){
	atype mm = GetMM(Arr, left, right);
	int index = left -1;
	for(int i = left ; i < right ; ++i){
		if(Arr[i] < mm){
			swap(Arr[++index] , Arr[i]);
		}
		if(Arr[i] == mm){
			swap(Arr[i], Arr[right]);
		}
	}
	swap(Arr[++index], Arr[right]);
	return index;
}

template <class atype>
atype LinearizeSelect<atype>::WorstConditionSelect(ArrayPtr Arr, const int size,
								const int left, const int right, const int index){
	if(left == right) return Arr[left];
	int mmIndex = MedianPartition(Arr, left, right);
	int status = mmIndex + 1;
	if(status == index){
		return Arr[mmIndex];
	}else if(status > index){
		return WorstConditionSelect(Arr, size, left, mmIndex-1, index); // 一定要用划分的index，而不是相对排名
	}else {
		return WorstConditionSelect(Arr, size, mmIndex + 1, right, index);
	}
}

template <class atype>
atype LinearizeSelect<atype>::ExSelect(ArrayPtr Arr, const int size, const int index){
	return ExpectSelect(Arr, size, 0, size-1, index);
}

template <class atype>
atype LinearizeSelect<atype>::WCSelect(ArrayPtr Arr, const int size, const int index){
	return WorstConditionSelect(Arr, size, 0, size-1, index);
}


#endif